#include <vector>
#include <string>
#include <iostream>
using namespace std;
class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        if(n == 1)
        	return vector<string>{"0","1"};
        vector<string> lastGray = getGray(n-1);
        vector<string> result(lastGray);
        for(auto iter = lastGray.end(); iter != lastGray.begin(); --iter)
        {
        	(*iter).insert(0,"1");
        	result.push_back(*iter);
        }
        return result;
    }
};


int main()
{
	GrayCode gc;
	vector<string> v = gc.getGray(2);
	for(const string &s : v)
		cout<<s<<endl;

	return 0;
}